class UnionFind:
    def __init__(self, n):
        """
        初始化并查集
        :param n: 并查集中元素的个数
        """
        # 用一个列表来存储每个元素的父节点，初始时每个元素的父节点是其自身
        self.parent = list(range(n))
        # 用一个列表来存储每个元素所在树的秩（可以理解为树的高度），初始时每个元素的秩为0
        self.rank = [0] * n

    def find(self, x):
        """
        查找元素x的根节点，使用路径压缩优化
        :param x: 要查找的元素
        :return: 元素x的根节点
        """
        if self.parent[x] != x:
            # 如果x的父节点不是自身，说明x不是根节点，进行路径压缩
            # 将x的父节点更新为根节点（递归查找并更新）
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """
        合并元素x和y所在的集合，使用按秩合并优化
        :param x: 要合并的元素之一
        :param y: 要合并的元素之一
        """
        root_x = self.find(x)  # 查找x的根节点
        root_y = self.find(y)  # 查找y的根节点

        if root_x != root_y:
            # 如果x和y的根节点不同，说明它们不在同一个集合中，进行合并
            if self.rank[root_x] < self.rank[root_y]:
                # 如果root_x的秩小于root_y的秩，将root_x的父节点设为root_y
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                # 如果root_x的秩大于root_y的秩，将root_y的父节点设为root_x
                self.parent[root_y] = root_x
            else:
                # 如果root_x和root_y的秩相等，将root_y的父节点设为root_x，并将root_x的秩加1
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
                # 初始化一个大小为10的并查集
uf = UnionFind(10)
print(uf.find(0) == uf.find(1))
print(uf.find(2) == uf.find(3))
uf.union(0, 1)
uf.union(2, 3)
uf.union(5, 6)
print(uf.find(0) == uf.find(1))
print(uf.find(2) == uf.find(3))
print(uf.find(5) == uf.find(6))
